﻿//-------------------------------------------------------------------
//	Copyright (c) 2010-2014  Zhirnov Andrey
//	This file is part of the "UX Standard Lib" project.
//	See copyright notice in "UX_STL_Ext.h".
//-------------------------------------------------------------------

#ifndef _UXS_FORWARD_LIST_H
#define _UXS_FORWARD_LIST_H

#pragma once

#include "TArray.h"

namespace UX_STL
{
namespace UXTypesExt
{

	#define TForwardList		forward_list
	#define RET_ERROR( _ret )	{ WARNING("error in forward_list");  return _ret; }
	#define RET_VOID			RET_ERROR( ; )
	

	template <typename T>
	struct TListConstructor
	{
		static void CreateDefault(T &e)		{}
		static void Create(T &e)			{}
		static void Destroy(T &e)			{}
		static void Copy(T &from, T &to)	{ to = from; }
	};



	//
	// Forward List
	//
	
	template <	typename T,
				typename C = TListConstructor<T>,
				template<typename> class S = TCopyStrategy,		// for array
				template<typename> class A = TAllocator			// for array
			 >
	struct TForwardList
	{
	private:
		//
		// First -> Node -> ... -> Node -> Last
		//
		
		//
		// Node
		//

		struct TNode
		{
			TNode *	pNext;	// 0x001 - marked for delete
			T		tElem;
			///
			TNode(): tElem(), pNext(null)
			{
				C::CreateDefault( tElem );
			}

			TNode(const T& value):
				tElem(value), pNext(null)
			{
				C::Create( tElem );
			}

			TNode(const TNode &node):
				tElem(node.tElem), pNext(node.pNext)
			{
				C::Create( tElem );
			}

			~TNode()
			{
				C::Destroy( tElem );
			}

			TNode & operator = (TNode &right)
			{
				C::Copy( right.tElem, tElem );
				return *this;
			}
		};
		
	public:

		// Node Iterator
		struct TNodeIter
		{
			friend struct TForwardList;

		private:
			TNode	*_ptr;

		public:
			TNodeIter(): _ptr(null) {}
			TNodeIter(TNode *p): _ptr(p) {}
			TNodeIter(const TNodeIter &iter): _ptr(iter._ptr) {}

			TNodeIter &	operator ++ ()
			{
				ASSERT( Valid() ); 
				_ptr = _ptr->pNext;
				return *this;
			}
			TNodeIter	operator ++ (int)
			{
				TNodeIter	node(*this);
				++(*this);
				return node;
			}
			TNodeIter &	operator =  (const TNodeIter & right)
			{
				_ptr = right._ptr;
				return *this;
			}
			TNodeIter &	operator >> (usize uStep)
			{
				ASSERT( Valid() ); 
				while ( uStep-- != 0 )	++(*this);
				return *this;
			}
			TNodeIter &	operator += (uint iStep)
			{
				return ( (*this) >> iStep );
			}

			bool		operator == (const TNodeIter & right)	const	{ return _ptr == right._ptr; }
			bool		operator != (const TNodeIter & right)	const	{ return _ptr != right._ptr; }
			TNodeIter	operator +  (int iStep)					const	{ return TNodeIter(*this) += iStep; }
			T *			operator -> ()									{ return &Elem(); }
			const T *	operator -> ()							const	{ return &Elem(); }

			bool		Valid()									const	{ return ( _ptr != null ); }
			bool		NextValid()								const	{ return ( _ptr->pNext != null ); }
			T		 &	Elem()											{ ASSERT( Valid() );  return _ptr->tElem; }
			const T	 &	Elem()									const	{ ASSERT( Valid() );  return _ptr->tElem; }
		};

		typedef TNodeIter							iterator;
		typedef T									value_t;
		typedef TForwardList<T,C,S,A>				Self;
		typedef array< TNode, S<TNode>, A<TNode> >	_node_array_t;

	private:
		_node_array_t	_aNodes;
		TNode	*		_pFirst,
				*		_pLast;
	
	private:
		void _OnResize(const TNode *pLastPtr)
		{
			isize	offset	= PointerOffset( _aNodes.ptr(), pLastPtr );
			_pFirst			= MovePointer( _pFirst, offset );
			_pLast			= MovePointer( _pLast,  offset );
			TNode *	p_node	= _pFirst;

			while ( p_node->pNext != null )
			{
				p_node->pNext = MovePointer( p_node->pNext, offset );
				p_node = p_node->pNext;
			}
		}	

	public:
		TForwardList(): _pFirst(null), _pLast(null)
		{
		}

		~TForwardList()
		{
			Clear();
		}

		iterator	First ()						const	{ return _pFirst; }
		iterator	Last ()							const	{ return _pLast; }
		bool		IsFirst (const iterator & node)	const	{ return ( node._ptr == _pLast ); }
		bool		IsLast (const iterator & node)	const	{ return ( node._ptr == _pFirst ); }
		bool		Empty()							const	{ return _pFirst == null; }
		usize		Count()							const	{ return _aNodes.Count(); }
		void		Clear()									{ _aNodes.Clear();  _pFirst = null;  _pLast = null; }


		template <typename U>
		bool  ForEach(U sUpd) const
		{
			TNode *	p_node = _pFirst;

			while ( p_node != null )
			{
				sUpd( p_node );
				p_node = p_node->pNext;
			}

			return true;
		}


		iterator  PushBack(const T& value)
		{
			if ( _aNodes.Empty() )
			{
				_aNodes.PushBack( TNode( value ) );
				_pFirst = _pLast = &_aNodes.Front();
				return _pLast;
			}

			TNode *	last_ptr = _aNodes.ptr();

			_aNodes.PushBack( TNode( value ) );

			// if array resized //
			if ( last_ptr != _aNodes.ptr() )
				_OnResize( last_ptr );

			_pLast->pNext = &_aNodes.Back();
			_pLast = _pLast->pNext;
			return _pLast;
		}


		iterator  PushFront(const T& value)
		{
			if ( _aNodes.Empty() )
			{
				_aNodes.PushBack( TNode( value ) );
				_pFirst = _pLast = &_aNodes.Front();
				return _pFirst;
			}

			TNode *	last_ptr = _aNodes.ptr();

			_aNodes.PushBack( TNode( value ) );

			// if array resized //
			if ( last_ptr != _aNodes.ptr() )
				_OnResize( last_ptr );

			last_ptr = _pFirst;
			_pFirst = &_aNodes.Back();
			_pFirst->pNext = last_ptr;
			return _pFirst;
		}


		iterator  Push(const T& value, bool bToFront = true)
		{
			// find deleted nodes
			TNode const *	p_deleted	= (TNode *)0x01;
			TNode *			p_node		= null;

			FOR( i, _aNodes )
			{
				if ( _aNodes[i]->pNext == p_deleted ) {
					p_node = &_aNodes[i];
					break;
				}
			}

			// if not found then create node
			if ( p_node == null )
			{
				if ( bToFront )	return PushFront( value );
				else			return PushBack( value );
			}

			// if found then add to front/back
			if ( bToFront )
			{
				p_node->pNext = _pFirst;
				_pFirst = p_node;
				return _pFirst;
			}
			else
			{
				_pLast->pNext = p_node;
				_pLast = _pLast->pNext;
				return _pLast;
			}
		}


		void  PopFront()
		{
			if ( _pFirst == null )
				RET_VOID;

			TNode *	temp = _pFirst->pNext;
			*_pFirst = TNode();
			_pFirst->pNext = (TNode *)0x01;
			_pFirst = temp;
		}


		void  PopBack()
		{
			if ( _pLast == null )
				RET_VOID;

			// find prev node //
			TNode *	p_node = _pFirst;

			while ( p_node->pNext != null and
					p_node->pNext->pNext != null /*and
					p_node->pNext->pNext->pNext != null*/ )
			{
				p_node = p_node->pNext;
			}

			/*if ( p_node == _pFirst )
			{
				//if ( p_node

				RET_VOID;
			}*/

			p_node->pNext = null;

			*_pLast = TNode();
			_pLast->pNext = (TNode *)0x01;
			_pLast = p_node;
		}

	
		void  Erase(iterator pIter)
		{
			if ( pIter == _pFirst )		return PopFront();
			if ( pIter == _pLast )		return PopBack();


			TNode *	p_node = _pFirst;

			while ( p_node->pNext != null )
			{
				if ( p_node->pNext == pIter._ptr )
				{
					p_node->pNext		= p_node->pNext->pNext;
					*pIter._ptr			= TNode();
					pIter._ptr->pNext	= (TNode *)0x01;
					return;
				}

				p_node = p_node->pNext;
			}
		}


		Self &  operator = (const TForwardList &right)
		{
			Clear();

			_aNodes = right._aNodes;

			isize	offset = PointerOffset( this->_aNodes.ptr(), right._aNodes.ptr() );

			TNode *	p_node = MovePointer( right._pFirst, offset );

			while ( p_node != null )
			{
				p_node->pNext = MovePointer( p_node->pNext, offset );
				p_node = p_node->pNext;
			}

			return *this;
		}


		bool  Replace(TForwardList &lList)
		{
			_swap( this->_pFirst,	lList._pFirst );
			_swap( this->_pLast,	lList._pLast );
			_aNodes.SetMem( lList._aNodes );
			return true;
		}
	};



	#undef TForwardList
	#undef RET_ERROR
	#undef RET_VOID
	
//-------------------------------------------------------------------

}	// UXTypesExt
}	// UX_STL

#endif	// _UXS_FORWARD_LIST_H
